#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 稀疏图 - 邻接表
template <typename Weight>
class SparseGraph{
	private:
		int n, m;
		bool directed;
		vector<vector<Edge<Weight> *>> g;
	
	public:
		SparseGraph(int n, bool directed){
			this->n = n;
			this->m = 0;
			this->directed = directed;
			for(int i = 0; i < n; ++i){
				// 初始时每个顶点没有相邻顶点
				// 每一个都是空的向量(也可以使用链表实现,删除元素更方便)
				g.push_back(vector<Edge<Weight> *>());
			}
		}

		~SparseGraph(){
			for(int i = 0;i < n; ++i){
				for(int j = 0; j < g[i].size(); ++j){
					delete g[i][j];
				}
			}
		}

		int V(){ return n;}
		int E(){ return m;}
		

		// 邻接表中 一般允许有平行边,处理成本高
		void addEdge(int v, int w, Weight weight){
			assert(v >= 0 && v < n);
			assert(w >= 0 && w < n);
				
			// 添加新元素 w 表示 v w 相连
			g[v].push_back(new Edge<Weight>(v, w, weight));
			// 如果是无向图, 还考虑了自环边
			if(v != w && !directed){
				g[w].push_back(new Edge<Weight>(w, v, weight));
			}
			m++;
		}

		// 判断是否有连接 ,也可以看成处理平行边 O(N)
		bool hasEdge(int v, int w){
			assert(v >= 0 && v < n);
			assert(w >= 0 && w < n);
			// 循环判断 是否有 v 到 w 的边
			for(int i = 0; i < g[v].size(); ++i){
				if(g[v][i]->other(v) == w){
					return true;
				}
			}
			return false;
		}
		
		void show(){
			for(int i = 0; i < n; ++i){
				cout << "vertex " << i << ":\t";
				for(int j = 0; j < g[i].size(); ++j){
					cout <<"( to:" <<  g[i][j]->w()<<",wt:"
						<< g[i][j]->wt()<< ")\t";
				}
				cout << endl;
			}
		}

		// 稀疏图相临边迭代器
		class adjIterator{
		private:
			SparseGraph &G;			// 存储图的引用
			int v;					// 存储图迭代的节点
			int index;				// 当前迭代到哪里
		public:
			/**
			 * 传入迭代图的引用 &graph
			 * 迭代图中那个节点
			 * 使用构造列表方式初始化
			 **/
			adjIterator(SparseGraph &graph, int v): G(graph){
				this->v = v;
				this->index = 0;
			}

			// 要迭代的第一个元素,找图中第一个节点
			Edge<Weight>*  begin(){
				index = 0;
				if(G.g[v].size()){
					return G.g[v][index];
				}
				return NULL;
			}

			// 当前迭代的元素找下一个元素
			Edge<Weight>* next(){
				index ++;
				if(index < G.g[v].size()){		// 没有越界
					return G.g[v][index];
				}
				return NULL;
			}

			// 迭代是否终止
			bool end(){
				return index >= G.g[v].size();  // 已经越界
			}
		};
};
